/**
 * @file   BinarySearchTree.h
 * @author Li Zhiqi 
 * @date   Sun Dec  6 09:30:08 2020
 * 
 * @brief  A binary search tree achievement which is basic of
 *         red-blach tree.
 * 
 */

#ifndef MGGS_BST
#define MGGS_BST

#define BLACK false
#define RED true

#include <iostream>
#include <cstdlib>
#include <algorithm>

template<typename T>
class BinaryTree
{
public:
  /** 
   * The node structure of the binary tree. Set all members as public
   * for efficiency.
   * 
   *
   */
    class Node
    {
    public:
      T data; /**< Satellite data. */
      Node* lc;/**<Left child. */
      Node* rc;/**< Right child. */
      Node* parent;/**< Parent. */
      bool color = RED; /**< Color,initially red. */
      /** 
       * Constructor. Create a node with the data is the given
       *  value _d.
       * 
       * @param _data Given value.
       */
      Node(T _data);
    };
 protected:
    Node* root;/**< The address of the root node. 
		*  Its parent is NULL. */
 public:
    /** 
     * Constructor,create an empty tree.
     * 
     */
    BinaryTree() {root = NULL;};
    /** 
     * Constructor. Create a new tree with only one root node, which
     * the the data inside is the given value _data.
     * 
     * @param _data Given value.
     */
    BinaryTree(T _data);
    /** 
     * Default destructor.
     * 
     */
    ~BinaryTree();
    /** 
     * Inorder walking and printing the sub-tree root at _x.
     * 
     * @param _x The root of the sub-tree.
     */
    void inorder_walk(Node* _x) const;
    /** 
     * Inorder walking and pass the first _l data into the array _arr.
     * 
     * @param _x The root of the sub-tree.
     * @param _arr The array passed in.
     * @param _l The number of data passed in.
     */
    void inorder_walk(Node* _x, T* _arr, int _l) const;
    /** 
     * Inorder walking and printing the whole tree from the root.
     * 
     */
    void inorder_walk() const;
    /** 
     * Inorder walking and pass data of the whole tree into array _arr.
     * 
     * @param _arr The array passed in.
     * @param _l The number of data passed in.
     */
    void inorder_sort_walk(T* _arr, int _l) const;
     /** 
     * Search the location of the node contains data _data. If there are
     * more than one nodes, return the first one met. 
     * 
     * @param _data The data for searching.
     * 
     * @return The address of the node contains _data, and NULL if not
     * found.
     */
    Node* tree_search(T _data) const;
    /** 
     * Find the node whose data is the minimum in sub-tree root at _x.
     * 
     * @param _x The root of the sub-tree.
     * 
     * @return The address of the node with the minimum.
     */
    Node* min(Node* _x) const;
    /** 
     * Find the node whose data is the maximum in sub-tree root at _x.
     * 
     * @param _x The root of the sub-tree.
     * 
     * @return The address of the node with the maximum.
     */
    Node* max(Node* _x) const;
    /** 
     * Find the node with the smallest data greater than the data of
     * _x.
     * 
     * @param _x The start node.
     * 
     * @return The address of the successor node.
     */
    Node* successor(Node* _x) const;
    /** 
     * Find the node with the largest data less than the data of
     * _x.
     * 
     * @param _x The start node.
     * 
     * @return The address of the predecessor node.
     */
    Node* predecessor(Node* _x) const;
    /** 
     * Delete the whole sub-tree root at _x, and release the memory.
     * 
     * @param _x The root of the sub-tree.
     */
    void release(Node* _x);
    /** 
     * Insert a new node to the binary search tree, and keep it as
     * a binary search tree.
     * 
     * @param _p The new node.
     */
    void insert(Node* _p);
    /** 
     * Insert a new node with data _data to the binary search tree, and
     * keep it as a binary search tree.
     * 
     * @param _data The data for the new node.
     */
    void insert(T _data);
    /** 
     * Trans plant the sub-tree root at _u to _v. 
     * 
     * @param _u The root of the source sub-tree.
     * @param _v The root place of the sub-tree trans planting to.
     */
    void transplant(Node *_u, Node *_v);
    /** 
     * Delete node _x in the binary search tree, and keep it as a
     * binary search tree.
     * 
     * @param _x The node to delete.
     */
    void del(Node *_x);
    /** 
     * Search node with data _data, delete it in the binary search tree, 
     * and keep it as a binary search tree. Do nothing if not found.
     *
     * 
     * @param _data The data of node to be delete.
     */
    void del(T _data);
    /** 
     * Rotate node _x to the right, and keep the structure of binary search
     * tree.
     * 
     * @param _x The node to be rotate.
     */
    void RightRotate(Node* _x);
    /** 
     * Rotate node _x to the left, and keep the structure of binary search
     * tree.
     * 
     * @param _x The node to be rotate.
     */
    void LeftRotate(Node* _x);
    /** 
     * Test search function.
     * 
     * @param _data The data to be search.
     */
    void test_search(T _data) const;
    /** 
     * Test successor function.
     * 
     */
    void test_successor() const;
    /** 
     * Test predecessor function.
     * 
     */
    void test_predecessor() const;
    /** 
     * Test min function.
     * 
     */
    void test_min() const;
    /** 
     * Test max function.
     * 
     */
    void test_max() const;
    /** 
     * Test del function.
     * 
     */
    void test_del();
    /** 
     * Test rightrotate function.
     * 
     */
    void test_rightrotate();
    /** 
     * Test leftrotate function.
     * 
     */
    void test_leftrotate();
};
/** 
 * Sort array arr with binary search tree.
 * 
 * @param arr The array to be sorted.
 * @param _l The length of array.
 */
template <typename T> void BST_sort(T* arr, int _l);


template<typename T>
BinaryTree<T>::BinaryTree(T _data)
{
    Node* p = new Node(_data);
    if (root == NULL)
	root = p;
};

template<typename T>
void BinaryTree<T>::release(Node* _x)
{
    if (_x != NULL)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};

template<typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
};

template<typename T>
BinaryTree<T>::Node::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::successor(Node* _x) const
{
    Node* x = _x;
    if (x->rc != NULL)
	return min(x->rc);
    Node* y = x->parent;
    while (y != NULL && x == y->rc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};

template<typename T>
void BinaryTree<T>::test_successor() const
{
    std::cout << "successor: " << successor(root->lc->lc->rc)->data << std::endl;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::predecessor(Node* _x) const
{
  Node* x = _x;
  if (x->lc != NULL)
    return max(x->lc);
  Node* y = x->parent;
  while (y != NULL && x == y->lc){
    x = y;
    y = y->parent;
  }
  return y;
}

template<typename T>
void BinaryTree<T>::test_predecessor() const
{
  std::cout << "predecessor: " << predecessor(root->rc->lc)->data << std::endl;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::min(Node* _x) const
{
    while (_x->lc != NULL)
	_x = _x->lc;
    return _x;
};

template<typename T>
void BinaryTree<T>::test_min() const
{
  std::cout << "min: " << min(root->lc)->data << std::endl;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::max(Node* _x) const
{
  while (_x->rc != NULL)
    _x = _x->rc;
  return _x;
}

template<typename T>
void BinaryTree<T>::test_max() const
{
  std::cout << "max: " << max(root)->data << std::endl;
};



template<typename T>
void BinaryTree<T>::inorder_walk(Node* _x) const
{
    if (_x != NULL)
    {
	inorder_walk(_x->lc);
	std::cout << _x->data << "  ";
	inorder_walk(_x->rc);
    }
};

template<typename T>
void BinaryTree<T>::inorder_walk(Node* _x, T* _arr, int _l) const
{
  static int k=0;
  if (_x != NULL)
    {
      inorder_walk(_x->lc,_arr,_l);
      if (k < _l){
	_arr[k]=_x->data;
	k++;
      }
      inorder_walk(_x->rc,_arr,_l);
    }
};

template<typename T>
void BinaryTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template<typename T>
void BinaryTree<T>::inorder_sort_walk(T* _arr, int _l) const
{
  inorder_walk(root,_arr,_l);
};

template<typename T>
void BinaryTree<T>::insert(Node* _p){
    Node* y = NULL;
    Node* x = root;
    while (x != NULL)
    {
	y = x;
	if (_p->data  < x->data)
	    x = x->lc;
	else
	    x = x->rc;
    }
    _p->parent = y;
    if (y == NULL)
	root = _p;
    else if (_p->data < y->data)
	y->lc = _p;
    else
	y->rc = _p;
}


template<typename T>
void BinaryTree<T>::insert(T _data)
{
    Node* p = new Node(_data);
    this->insert(p);
}


template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::tree_search(T _data) const
{
  Node* x = root;
  while (x != NULL){
    if (x->data > _data)
      x = x->lc;
    else if (x->data < _data)
      x = x->rc;
    else
      return x;
  }
  return NULL;
}


template<typename T>
void BinaryTree<T>::test_search(T _data) const
{
  Node* p = tree_search(_data);
  if (p == NULL)
    std::cout << "Not Found" << std::endl;
  else{
    if (p->parent == NULL)
      std::cout << "root!" << std::endl;
    else
      std::cout << "parent:" << p->parent->data << std::endl;
    if (p->lc != NULL)
      std::cout << "left child:" << p->lc->data << std::endl;
    if (p->rc != NULL)
      std::cout << "right child:" << p->rc->data << std::endl;
  }
};

template <typename T> void BST_sort(T* _arr, int _l){
  BinaryTree<T> A;
  std::random_shuffle(_arr,_arr+_l);
  for (int i=0; i<_l ; i++)
    A.insert(_arr[i]);
  A.inorder_sort_walk(_arr,_l);
}

template<typename T>
void BinaryTree<T>::transplant(Node *_u, Node *_v){
  if (_u == NULL){
    std::cerr << "Error! Can not transplant to a NULL."
                  << std::endl;
    std::exit(-1);
  }
  if (_u->parent == NULL)
    root = _v;  
  else if (_u == _u->parent->lc)
    _u->parent->lc = _v;
  else
    _u->parent->rc = _v;
  if (_v != NULL)
    _v->parent = _u->parent;
}

template<typename T>
void BinaryTree<T>::del(Node *_x){
  if (_x != NULL){
    if (_x->lc == NULL)
      this->transplant(_x, _x->rc);
    else if (_x->rc == NULL)
      this->transplant(_x, _x->lc);
    else{
      Node *y = min(_x->rc);
      if (y->parent != _x){
	this->transplant(y, y->rc);
	y->rc = _x->rc;
	y->rc->parent = y;
      }
      this->transplant(_x, y);
      y->lc = _x->lc;
      y->lc->parent = y;
    }
    delete _x;
  }
}


template<typename T>
void BinaryTree<T>::del(T _data){
  Node* y = this->tree_search(_data);
  this->del(y);  
}


template<typename T>
void BinaryTree<T>::test_del(){
  this->del(root->rc);
}

template<typename T>
void BinaryTree<T>::RightRotate(Node* _x){
  Node* y = _x->lc;
  _x->lc = y->rc;
  if (y->rc != NULL)
    y->rc->parent = _x;
  y->parent = _x->parent;
  if (_x->parent == NULL)
    root = y;
  else if (_x == _x->parent->lc)
    _x->parent->lc = y;
  else
    _x->parent->rc = y;
  y->rc = _x;
  _x->parent = y;
}


template<typename T>
void BinaryTree<T>::LeftRotate(Node* _x){
  Node* y = _x->rc;
  _x->rc = y->lc;
  if (y->lc != NULL)
    y->lc->parent = _x;
  y->parent = _x->parent;
  if (_x->parent == NULL)
    root = y;
  else if (_x == _x->parent->lc)
    _x->parent->lc = y;
  else
    _x->parent->rc = y;
  y->lc = _x;
  _x->parent = y;
}

template<typename T>
void BinaryTree<T>::test_rightrotate(){
  this->RightRotate(root->rc);
}

template<typename T>
void BinaryTree<T>::test_leftrotate(){
  this->LeftRotate(root);
}


#else
// DO NOTHING.
#endif
